#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int cal_op(string &a, string &b, int i, int j)
{
        if(i == 0){
                return j;
        }
        if(j == 0){
                return i;
        }

        if(a[i - 1] == b[j - 1]){
                return cal_op(a, b, i - 1, j - 1);
        }else{
                int op1 = cal_op(a, b, i - 1, j) + 1;
                int op2 = cal_op(a, b, i - 1, j - 1) + 1;
                int op3 = cal_op(a, b, i, j - 1) + 1;
                return min({op1, op2, op3});
        }
        return 0;
}

int cal_op(string &a, string &b, int i, int j, vector<vector<int>> &recd)
{
        if(i == 0){
                return j;
        }
        if(j == 0){
                return i;
        }

        if(recd[i][j] != -1){
                return recd[i][j];
        }

        if(a[i - 1] == b[j - 1]){
                return recd[i][j] = cal_op(a, b, i - 1, j - 1, recd);
        }else{
                int op1 = cal_op(a, b, i - 1, j, recd) + 1;
                int op2 = cal_op(a, b, i - 1, j - 1, recd) + 1;
                int op3 = cal_op(a, b, i, j - 1, recd) + 1;
                return recd[i][j] = min({op1, op2, op3});
        }
        return 0;
}

int cal_op(string &a, string &b)
{
        vector<vector<int>> dp(a.length() + 1, vector<int>(b.length() + 1, 0));
        for(int i = 0; i <= b.length(); i++){
                dp[0][i] = i;
        }
        for(int i = 0; i <= a.length(); i++){
                dp[i][0]  = i;
        }

        for(int i = 1; i <= a.size(); i++){
                for(int j = 1; j <= b.size(); j++){
                        if(a[i - 1] == b[j - 1]){
                                dp[i][j] = dp[i - 1][j - 1];
                        }else{
                                dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                        }
                }
        }

        return dp.back().back();
}

int cal_op_sp(string &a, string &b)
{
        vector<int> dp(b.size() + 1, 0);
        for(int i = 0; i <= b.size(); i++){
                dp[i] = i;
        }

        int lu = 0, bk = 0;
        for(int i = 1; i <= a.size(); i++){
                lu = dp[0];
                dp[0] = i;
                for(int j = 1; j <= b.size(); j++){
                        bk = dp[j];
                        if(a[i - 1] == b[j - 1]){
                                dp[j] = lu;
                        }else{
                                dp[j] = min({dp[j], dp[j - 1], lu}) + 1;
                        }
                        lu = bk;
                }
        }

        return dp.back();
}

int main()
{
        string s1, s2;
        cin>>s1>>s2;
        vector<vector<int>> recd(s1.size() + 1, vector<int>(s2.size() + 1, -1));
        cout<<cal_op_sp(s1, s2)<<endl;
        return 0;
}